Universal Hashing

定义 Definition

通用哈希（universal hashing）：一种构造或选择哈希函数的方法——从一个“哈希函数族”中随机挑选一个哈希函数，使得对任意两个不同的键，它们发生哈希冲突的概率都被良好地上界控制（通常约为 (1/m)，其中 (m) 是哈希表大小）。它常用于降低“对抗性输入”导致的大量冲突风险，是随机化算法中的经典思想。
（该术语在不同教材中也可能涉及“强通用/两两独立”等更细分概念。）

发音 Pronunciation (IPA)

/ˌjuːnɪˈvɜːrsəl ˈhæʃɪŋ/

例句 Examples

Universal hashing helps prevent an attacker from forcing many collisions.
通用哈希有助于防止攻击者刻意制造大量哈希冲突。

By selecting a hash function at random from a universal family, the expected time for search in a hash table remains close to constant even under adversarial input distributions.
通过从通用哈希函数族中随机选择一个哈希函数，即使在对抗性的输入分布下，哈希表查找的期望时间也能保持接近常数。

词源 Etymology

universal 源自拉丁语 universalis（“普遍的、通用的”）；hashing 来自 hash（原义与“切碎/混杂”相关），在计算机科学中指把键映射到固定范围的“散列/哈希”。“universal hashing”这一术语在算法研究中用于强调：使用一个“足够广泛、性质受控”的哈希函数集合，并通过随机选择来获得普遍（对任意输入都较稳健）的性能保证。

相关词 Related Words

• Hash Function
• Hash Table
• Collision
• Randomized Algorithm
• Pairwise Independence
• Carter–Wegman Hashing
• Perfect Hashing
• Load Factor

文学与经典著作 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在哈希表与随机化分析章节中讨论通用哈希。
• Randomized Algorithms（Motwani & Raghavan）：介绍通用哈希作为随机化技术的重要例子。
• “Universal Classes of Hash Functions”（Carter & Wegman, 1979）：提出并系统化通用哈希函数族思想的经典论文。
• The Design and Analysis of Computer Algorithms（Aho, Hopcroft, Ullman）：在哈希与算法分析相关内容中提及通用哈希思想与冲突概率控制。